package com.lw.leetcode.tree.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * tree
 * 2416. 字符串的前缀分数和
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/20 9:55
 */
public class SumPrefixScores {

    public static void main(String[] args) {
        SumPrefixScores test = new SumPrefixScores();

        // [5,4,3,2]
//        String[] arr = {"abc", "ab", "bc", "b"};

        // [4]
//        String[] arr = {"abcd"};

        //
        String[] arr = Utils.getStrs(1000, 1000, 'a', 'z');

        int[] ints = test.sumPrefixScores(arr);
        System.out.println(Arrays.toString(ints));
    }

    public int[] sumPrefixScores(String[] words) {
        Node root = new Node();
        for (String word : words) {
            find(word, 0, root);
        }
        int length = words.length;
        int[] values = new int[length];
        for (int i = 0; i < length; i++) {
            values[i] = getCount(words[i], 0, root);
        }
        return values;
    }

    private int getCount(String str, int index, Node node) {
        if (str.length() == index) {
            return 0;
        }
        Node no = node.arr[str.charAt(index) - 'a'];
        return getCount(str, index + 1, no) + no.count;
    }

    private void find(String str, int index, Node node) {
        if (str.length() == index) {
            return;
        }
        int v = str.charAt(index) - 'a';
        Node no = node.arr[v];
        if (no == null) {
            no = new Node();
            node.arr[v] = no;
        }
        no.count++;
        find(str, index + 1, no);
    }

    private static class Node {
        private int count;
        private Node[] arr = new Node[26];
    }

}
